package 链表;

import java.util.List;

// https://leetcode-cn.com/problems/palindrome-linked-list/solution/
// 1->2->2->1 => true
public class _234_回文链表 {
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 1.快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2.反转后续节点
        ListNode nhead = reverse(slow);

        // 3.判断
        while(nhead != null) {
            if (head.val != nhead.val) {
                return false;
            }
            head = head.next;
            nhead = nhead.next;
        }

        return true;
    }

    public static ListNode reverse(ListNode head) {
        if (head.next == null) return head;

        ListNode newHead = reverse(head.next);
        newHead.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        System.out.println(isPalindrome(head));
    }
}
